package packageshipping;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * Not sure whether its correct or not
 * @author Seabook
 *
 */
public class PackageShipping {
	List<Route> routeList = new ArrayList<Route>();
	List<Route> fullRoutePath = new ArrayList<Route>();

	private static final String[] TEST_DATA1 = new String[] {
			"SANFRAN CHICAGO 20 3 0.4",

			"SANFRAN MEMPHIS 30 5 1.0", "CHICAGO NEWYORK 15 2 2.0",
			"MEMPHIS NEWYORK 8 6 0.1" };

	public static void main(String[] args) {
		PackageShipping ps = new PackageShipping();
		System.out.println(ps.ship(TEST_DATA1, "SANFRAN", "NEWYORK", 100, 100));
		System.out.println(ps
				.ship(TEST_DATA1, "SANFRAN", "NEWYORK", 100, 10000));
		System.out
				.println(ps.ship(TEST_DATA1, "SANFRAN", "NEWYORK", 36, 10000));
	}

	public void printRoutePath() {
		for (Route route : fullRoutePath) {
			System.out.println(route);
		}
	}

	public double ship(String[] routes, String origin, String destination,
			int time, int packageCost) {
		parseRoutes(routes);
		findAllWays(origin, destination);
		return calculatePaths(time, packageCost);
	}

	private double calculatePaths(int time, int pkgCost) {
		double bestCost = Double.MAX_VALUE;
		for (Route rout : fullRoutePath) {
			boolean exceedTime = false;
			int totalTime = 0;
			double totalCost = 0d;
			Route tmp = rout;
			totalTime += rout.time;
			if (totalTime > time) {
				continue;
			}
			totalCost += rout.cost;
			totalCost += pkgCost * rout.perToDamage / 100d;
			while (tmp.hasNext()) {
				tmp = rout.next;
				totalTime += tmp.time;
				totalCost += tmp.cost;
				totalCost += pkgCost * tmp.perToDamage / 100d;
				if (totalTime > time) {
					exceedTime = true;
					break;
				}
			}

			if (exceedTime) {
				continue;
			}

			if (totalCost < bestCost) {
				bestCost = totalCost;
			}
		}
		return bestCost;

	}

	private void findAllWays(String origin, String dest) {
		for (Route route : routeList) {
			if (origin.equals(route.from)) {
				route.isSearched = true;
				linkNextRoute(route, routeList, dest);
				fullRoutePath.add(route);
				clearIsSearchedMark();
			}
		}
	}

	private void clearIsSearchedMark() {
		for (Route route : routeList) {
			if (route.isSearched == true)
				route.isSearched = false;
		}

	}

	private void linkNextRoute(Route route, List<Route> routeList,
			String destination) {
		for (Route tmpRoute : routeList) {
			if (tmpRoute.isSearched) {
				continue;
			}

			if (tmpRoute.from.equals(route.to)) {
				route.next = tmpRoute;
				tmpRoute.isSearched = true;
				if (destination.equals(tmpRoute.to)) {
					return;
				}
				linkNextRoute(tmpRoute, routeList, destination);
			}
		}
	}

	private void parseRoutes(String[] routes) {
		for (String route : routes) {
			String[] routeElems = route.split(" ");
			Route aRoute = new Route(routeElems[0], routeElems[1],
					Integer.valueOf(routeElems[2]),
					Integer.valueOf(routeElems[3]),
					Double.valueOf(routeElems[4]));
			routeList.add(aRoute);
		}
	}
}

class Route implements Iterator<Route> {
	String from;
	String to;
	int time;
	double cost;
	double perToDamage;
	Route next;
	boolean isSearched = false;

	public Route() {

	}

	public Route(String from, String to, int time, int cost, double perToDamage) {
		this.from = from;
		this.to = to;
		this.time = time;
		this.cost = cost;
		this.perToDamage = perToDamage;
	}

	@Override
	public boolean hasNext() {
		if (this.next != null) {
			return true;
		}
		return false;
	}

	@Override
	public Route next() {
		return this.next;
	}

	@Override
	public void remove() {
		// TODO Auto-generated method stub
	}
}
